/**
 * \file    builder.cpp
 * \brief   Build the action table from a generator.
 * \author  Jérôme LAURENS
 * \version 0.1
 * \date    October 2, 2014
 *
 * Reads a LALR(1) grammar, generates a parser based on a template file.
 * This is based on lemon parser generator, but has strongly been
 * revisited.
 *
 */

#include "builder.h"
#include "generator.h"
#include "coder.h"

LPP_NAMESPACE_BEGIN

ActionOffset Builder::min_reduce_offset() const {
    return min_non_terminal_offset_m - generator().grammar()->number_of_lookahead_symbols();
}
ActionOffset Builder::min_shift_offset() const {
    return min_terminal_offset_m - generator().grammar()->number_of_lookahead_symbols();
}

Builder::ActionsProxy::ActionsProxy(StateRef const & state
                , bool const is_terminal
                , ActionIndex const index)
        : index_m(index)
        , state_m(state)
        , is_terminal_m(is_terminal)
        , number_of_actions_m(is_terminal?state->terminal_actions_count():state->non_terminal_actions_count()) {
    std::ostringstream oss;
    for (auto const & value: actions()) {
        oss<<Description()(value.second)<<"/";
    }
    DEBUG_MESSAGE("AP(%lu): %s", number_of_actions_m, oss.str().c_str());
}

bool Builder::ActionsProxy::is_terminal() const {
    return is_terminal_m;
}
ActionIndex Builder::ActionsProxy::number_of_actions() const {
    return number_of_actions_m;//cached value
}
bool Builder::ActionsProxy::operator < (ActionsProxy const& rhs) const {
    if (number_of_actions_m>rhs.number_of_actions_m) return true;
    if (number_of_actions_m<rhs.number_of_actions_m) return false;
    if (index_m>rhs.index_m) return true;
    return false;
}

ActionRefMap const & Builder::ActionsProxy::actions() const {
    return is_terminal_m? state_m->terminal_actions()
                        : state_m->non_terminal_actions();
}

ActionOffset & Builder::ActionsProxy::offset() const {
    return is_terminal_m? state_m->terminal_offset()
                        : state_m->non_terminal_offset();
}

/*!
 * \brief Build the actions table
 *
 * [detailed description]
 *
 * \param[in] None
 * \param[out] None
 * \return No return value
 * \sa prepare_output
 * \note [any note about the function you might have]
 * \warning This must be done prior to prepare_output
 */
Builder::Builder(Generator &generator)
    : generator_m(generator)
    , max_terminal_offset_m(0)//(std::numeric_limits<ActionOffset>().min())
    , min_terminal_offset_m(0)//(std::numeric_limits<ActionOffset>().max())
    , max_non_terminal_offset_m(0)//(std::numeric_limits<ActionOffset>().min())
    , min_non_terminal_offset_m(0)//(std::numeric_limits<ActionOffset>().max()
    , number_of_actions_m(0)
    , coder_m(*this)
{
#ifndef NDEBUG
//  build the simple action table
    for (StateRef const & state: generator.states()) {
        ActionRefMap As;
        for (ActionRef const & action: state->actions()) {
            As.emplace(action->lookahead(),action);
        }
        SymbolRefList Ls = generator.grammar()->lookahead_symbols();
        std::sort(Ls.begin(),Ls.end(),[](SymbolRef const & l,SymbolRef const & r)->bool{return l->index()<r->index();});
        for (SymbolRef const & lookahead: Ls) {
            if (As.count(lookahead)) {
                coder().simple_encode(state,As.at(lookahead));
            } else {
                coder().simple_encode(state,std::make_shared<Action>(Action::Type::ERROR,lookahead));
            }
        }
    }
#endif
#ifndef LPP_NO_DEFAULT_ACTIONS
    for (StateRef & state: generator.states()) {
        state->setup_default_actions();
    }
#endif
    /* Sort the states by number of actions,
     * either terminal or non terminal ones.
     * The ActionsProxy struct serves that purpose. */
    /* Compute the actions on all states and sort them */
    std::vector<ActionsProxy> APs;
    DEBUG_MESSAGE("NUMBER OF BUILT STATES: %lu",generator.states().size());
    for (StateRef const & state: generator.states()) {
        APs.emplace_back(state,true,APs.size());
        APs.emplace_back(state,false,APs.size());
    }
    std::sort(APs.begin(),APs.end(),[](ActionsProxy const & lhs, ActionsProxy const & rhs)->bool{
        return lhs<rhs;
    });
#ifndef NDEBUG
    DEBUG_MESSAGE("NUMBER OF ACTION PROXIES: %lu",APs.size());
    for (ActionsProxy const & proxy: APs) {
        DEBUG_MESSAGE("State: %ld, %sterminal actions: %ld",
                      proxy.state()->index(),
                      proxy.is_terminal()?"":"non ",
                      proxy.is_terminal()?proxy.state()->terminal_actions_count():
                      proxy.state()->non_terminal_actions_count());
    }
#endif
    /* Compute the action table.  In order to try to keep the size of the
    ** action table to a minimum, the heuristic of placing the largest action
    ** proxy first is used.
    */

    DEBUG_MESSAGE("error action code: %lu",generator.error_action_code());
    // A transaction set is gathering information about all the actions of a state,
    // either terminal ot non terminal ones.
    // We collect all the transactions sets by real offset in the final action map.
    // Then we collect all these intermediate maps by transaction set size.
    // This allows a faster comparision between transaction sets.
    // The global action map is built at the same time.
    typedef std::map<Index,TransactionSet> myMap; // slot -> transaction set
    typedef std::map<Index,myMap> myMapOfMap;
    myMapOfMap pre_map;
    Index max_used_slot=0;
    std::vector<ActionOffset> offsets;
    ActionOffset min_offset = std::numeric_limits<ActionCode>().max();
    DEBUG_MESSAGE("==========  BUILD ACTIONS TABLE...");
    for (ActionsProxy const & proxy: APs) {
        if (proxy.actions().size()==0) {
            // all forthcoming proxies won't have any actions
            break;
        } else {
            DEBUG_MESSAGE("===== ACTION TABLE proxy state: %lu is terminal: %s",
                          proxy.state()->index(),(proxy.is_terminal()?"YES":"NO"));
            TransactionSet Ts;
            for (ActionRefMap::value_type const & value: proxy.actions()) {
                ActionCode const code = coder().code(value.second);
                Ts.add_transaction(value.second, value.first->index(), code);
            }
            bool insert_in_action_map = false;
            TransactionIndex min_slot = 0;
            ActionOffset offset = 0;
            if (pre_map.count(Ts.size())) {
                DEBUG_MESSAGE("ACTION TABLE not empty");
                // the global action map is not empty
                // max_used_slot>0
                // either we find a duplicate, a hole or append the transactions set.
                myMap & M = pre_map.at(Ts.size());
                bool duplicate = false;
                for (myMap::value_type const & value: M) {
                    if ((duplicate = (value.second==Ts))) {
                        // duplicate is found
                        insert_in_action_map = false;
                        min_slot = value.first;
                        break;
                    }
                }
                if (!duplicate) {
                    DEBUG_MESSAGE("NOT A DUPLICATE");
                    // find a hole to insert the global action map
                    // We insert in slots such that
                    // min_slot<=slot<max_slot (optimal bounds)
                    // min_slot + amplitude = max_slot
                    // Actually slots 0 and max_used_slot-1 are already used
                    // The last possible index for a hole is < max_used_slot-1
                    // The first one is > 0
                    // we must have
                    // 0 < min_slot < max_used_slot
                    min_slot = 1;
                    while (true) {
                        assert(min_slot<=std::numeric_limits<TransactionIndex>().max()-Ts.amplitude());
                        bool no_hole = true;
                        for (Transaction const & T: Ts.transactions()) {
                            TransactionIndex slot = min_slot + (T.lookahead()-Ts.min_lookahead());
                            if ((no_hole = (action_table_m.count(slot)!=0))) {
                                break;
                            }
                        }
                        if (!no_hole) {
                            // This transaction set is not a duplicate:
                            // the offset must be new to avoid collisions
                            ActionOffset offset = min_slot - Ts.min_lookahead();
                            DEBUG_MESSAGE("HOLE CANDIDATE OFFSET: %ld",offset);
                            for (ActionOffset const & O: offsets) {
                                DEBUG_MESSAGE("ALREADY OFFSET   : %ld",O);
                                if ((no_hole=(offset==O))) {
                                    DEBUG_MESSAGE("SAME OFFSET");
                                    break;
                                }
                            }
                            if (!no_hole) {
                                break;
                            }
                        }
                        ++min_slot;
                    }
                    // we find a place to insert the transaction set
                    // either a hole or the end
                    M.emplace(min_slot,Ts);
                    insert_in_action_map = true;
                } else {
                    DEBUG_MESSAGE("DUPLICATE FOUND");
                    insert_in_action_map = false;
                }
            } else {
                DEBUG_MESSAGE("ACTION TABLE EMPTY");
                myMap M;
                min_slot = max_used_slot;
                M.emplace(min_slot,Ts);
                pre_map.emplace(Ts.size(),M);
                insert_in_action_map = true;
            }
            proxy.offset() = min_slot - Ts.min_lookahead();
            if (insert_in_action_map) {
                DEBUG_MESSAGE("INSERT IN ACTION MAP AT SLOT: %ld", min_slot);
                // no duplicate found: the Ts must be inserted in the action_map
                for (Transaction const & T: Ts.transactions()) {
                    TransactionIndex k = min_slot + (T.lookahead() - Ts.min_lookahead());
                    assert(action_table_m.count(k)==0);
                    action_table_m.emplace(k, T);
                    DEBUG_MESSAGE("%s",(Format("%1%->(%2%,%3%)")%k%T.lookahead()%T.action()).str().c_str());
                }
                TransactionIndex max_slot = min_slot + Ts.amplitude();
                if (max_used_slot<max_slot) {
                    max_used_slot = max_slot;
                }
                offsets.push_back(proxy.offset());
                for (ActionOffset const & O: offsets) {
                    DEBUG_MESSAGE("OFFSET: %ld",O);
                }
                if (proxy.offset()<min_offset) {
                    min_offset = proxy.offset();
                }
            }
            StateRef const & state = proxy.state();
#ifndef NDEBUG
            DEBUG_MESSAGE("==== TESTING TRANSACTION SET OF STATE: %ld",state->index());
            for (ActionRef const & action: state->actions()) {
                if (proxy.is_terminal()==action->lookahead()->is_terminal()) {
                    DEBUG_MESSAGE("STATE OFFSET: %ld", proxy.is_terminal()? state->terminal_offset(): state->non_terminal_offset());
                    ActionRef const A = coder().action(state,action->lookahead());
                    DEBUG_MESSAGE("INSERTED ACTION: (%lu,%s/%lu)=>%s", state->index(),action->lookahead()->name().c_str(),action->lookahead()->index(), Description()(A).c_str());
                    if (A!=action) {
                        DEBUG_MESSAGE("%s != %s", Description()(action).c_str(), Description()(A).c_str());
                        throw std::logic_error("Bad insterted transaction.");
                    } else {
                        DEBUG_MESSAGE("%s == %s", Description()(action).c_str(), Description()(A).c_str());
                    }
                }
            }
#endif
#ifndef NDEBUG
            DEBUG_MESSAGE("===== TESTING INTERMEDIATE ACTIONS");
            for (String const & s: built_actions(false)) {
                DEBUG_MESSAGE("INTERMEDIATE BUILT ACTION %s",s.c_str());
            }
            DEBUG_MESSAGE("state terminal offset: %ld",state->terminal_offset());
            DEBUG_MESSAGE("state non terminal offset: %ld",state->non_terminal_offset());
            ActionRefMap const & actions = proxy.is_terminal() ? state->terminal_actions(): state->non_terminal_actions();
            std::set<Transaction const> expected_actions;
            for (ActionRefMap::value_type const & value: actions) {
                expected_actions.insert(Transaction(value.first->index(),coder().code(value.second)));
            }
            std::set<Transaction const> inserted_actions;
            for (SymbolRef const & lookahead: generator.grammar()->lookahead_symbols()) {
                ActionRef a = coder().action(state,lookahead);
                if (!a->is_error()) {
                    if (proxy.is_terminal() == lookahead->is_terminal()) {
                        inserted_actions.insert(Transaction(a->lookahead_index(),coder().code(a)));
                    }
                } else {
                    DEBUG_MESSAGE("Error action: %s",lookahead->name().c_str());
                }
            }
            if (expected_actions!=inserted_actions) {
                DEBUG_MESSAGE("EXPECTED:");
                for (Transaction const & t: expected_actions) {
                    DEBUG_MESSAGE("%lu, %lu",t.action(),t.lookahead());
                }
                DEBUG_MESSAGE("INSERTED:");
                for (Transaction const & t: inserted_actions) {
                    DEBUG_MESSAGE("%lu, %lu",t.action(),t.lookahead());
                }
            }
#endif
            if (proxy.is_terminal()) {
                if (offset<min_terminal_offset_m) min_terminal_offset_m = offset;
                if (offset>max_terminal_offset_m) max_terminal_offset_m = offset;
            } else {
                if (offset<min_non_terminal_offset_m) min_non_terminal_offset_m = offset;
                if (offset>max_non_terminal_offset_m) max_non_terminal_offset_m = offset;
            }
        }
    }
    // Complete the table with safe error action generating codes
#warning Possible capacity exceeded below
    min_offset -= generator.grammar()->number_of_lookahead_symbols();
    TransactionIndex slot = 0;
    while (slot<max_used_slot) {
        if (!action_table_m.count(slot)) {
            action_table_m.emplace(slot,Transaction(generator.grammar()->default_symbol_index(),min_offset));
        }
        ++slot;
    }
#ifndef NDEBUG
    for (StateRef const & state: generator.states()) {
        DEBUG_MESSAGE("State #%lu", state->index());
        for (SymbolRef const & lookahead: generator.grammar()->lookahead_symbols()) {
            ActionRef const action = coder().action(state,lookahead);
            DEBUG_MESSAGE("%s => %s",lookahead->name().c_str(),Description()(action).c_str());
        }
    }
#endif
}

#ifndef NDEBUG
StringSet const Builder::built_actions_2(bool all) const {
    StringSet output;
    std::vector<ActionIndex> actions;
    for (Transactions::value_type const & value: action_table_m) {
        ActionIndex what = value.second.action();
        if (what > generator().error_action_code()) {
            what = generator().error_action_code();
        }
        while (actions.size()<=value.first) {
            actions.push_back(generator().error_action_code());
        }
        actions[value.first] = what;
        DEBUG_MESSAGE("MAP: %ld->(%ld,%ld)",value.second.lookahead(),value.first,what);
    }
    for (ActionIndex const i: actions) {
        DEBUG_MESSAGE("ACTIONS: %ld",i);
    }
    std::vector<SymbolIndex> lookaheads;
    for (Transactions::value_type const & value: action_table_m) {
        ActionIndex what = value.second.lookahead();
        if (what > generator().grammar()->number_of_lookahead_symbols()) {
            what = generator().grammar()->number_of_lookahead_symbols();
        }
        while (lookaheads.size()<=value.first) {
            lookaheads.push_back(generator().grammar()->number_of_lookahead_symbols());
        }
        lookaheads[value.first] = what;
    }
    for (SymbolIndex const i: lookaheads) {
        DEBUG_MESSAGE("LOOKAHEADS: %ld",i);
    }
    for (StateRef const & state: generator().states()) {
        DEBUG_MESSAGE("0) TESTING %s",Description()(state,1).c_str());
        ActionOffset offset = std::max(
                      min_shift_offset()
                    , state->terminal_offset());
        DEBUG_MESSAGE("offset: %ld",offset);
        for (SymbolRef const & s: generator().grammar()->shift_symbols()) {
            Format F("(%1%/%2%,%3%)=>%4%");
            F%state->index()%state->id();
            F%s->name();
            ActionIndex i = offset+s->index();
            if ((offset>=0||s->index()>=static_cast<Index>(-offset)) && i<actions.size() && lookaheads[i]==s->index()) {
//                DEBUG_MESSAGE("Map data IS good");
                ActionIndex code = actions[i];
                ActionRef const action = coder().action(code,s);
#ifndef NDEBUG
                ActionRef const & B = state->action(s);
                if (action != B && (!action->is_error()||(B))) {
                    DEBUG_MESSAGE("%s != %s",Description()(action).c_str(),Description()(B).c_str());
                    ActionRef const AA = coder().action(code,s);
                    throw std::logic_error("MAP IS BAD");
                }
#endif
                F%Description()(action,0);
                if  (!all) {
                    output.insert(F.str());
                }
            } else {
                F%Description()(std::make_shared<Action>(Action::Type::ERROR,s),0);
            }
            if  (all) {
                output.insert(F.str());
            }
        }
        offset = std::max(
                      min_reduce_offset()
                    , state->non_terminal_offset());
        for (SymbolRef const & s: generator().grammar()->reduce_symbols()) {
            Format F("(%1%/%2%,%3%)=>%4%");
            F%state->index()%state->id();
            F%s->name();
            ActionOffset i = s->index()+offset;
            if (i>=0 && static_cast<size_t>(i)<actions.size() && lookaheads[i]==s->index()) {
                ActionIndex code = actions[i];
                ActionRef const action = coder().action(code,s);
#ifndef NDEBUG
                ActionRef const & B = state->action(s);
                if (action != B && (!action->is_error()||(B))) {
                    DEBUG_MESSAGE("%s != %s",Description()(action).c_str(),Description()(B).c_str());
                    ActionRef const AA = coder().action(code,s);
                    throw std::logic_error("MAP IS BAD");
                }
#endif
                F%Description()(action,0);
                if (!all) {
                    output.insert(F.str());
                }
            } else {
                F%Description()(std::make_shared<Action>(Action::Type::ERROR,s),0);
            }
            if (all) {
                output.insert(F.str());
            }
        }
    }
    return output;
}
StringSet const Builder::built_actions(bool all) const {
    StringSet output;
    for (StateRef const & state: generator().states()) {
        DEBUG_MESSAGE("0) TESTING %s",Description()(state,1).c_str());
        for (SymbolRef const & s: generator().grammar()->lookahead_symbols()) {
            ActionOffset offset = s->is_terminal()?
                        std::max(min_shift_offset(), state->terminal_offset())
                      : std::max(min_reduce_offset(), state->non_terminal_offset());
            Format F("(%1%/%2%,%3%)=>%4%");
            F%state->index()%state->id();
            F%s->name();
            ActionIndex i = offset+s->index();
            if (action_table_m.count(i)) {
                Transaction T = action_table_m.at(i);
                if (T.lookahead()==s->index()) {
                    ActionRef const action = coder().action(T.action(),s);
                    F%Description()(action,0);
                    output.insert(F.str());
                } else if (all) {
                    F%Description()(std::make_shared<Action>(Action::Type::ERROR,s),0);
                    output.insert(F.str());
                }
            } else if (all) {
                F%Description()(std::make_shared<Action>(Action::Type::ERROR,s),0);
                output.insert(F.str());
            }
        }
    }
    return output;
}
StringSet const Builder::built_actions_1(bool all) const {
    StringSet output;
    for (StateRef const & state: generator().states()) {
        DEBUG_MESSAGE("0) TESTING %s",Description()(state,1).c_str());
        ActionOffset offset = std::max(
                      min_shift_offset()
                    , state->terminal_offset());
        DEBUG_MESSAGE("offset: %ld",offset);
        for (SymbolRef const & s: generator().grammar()->shift_symbols()) {
            Format F("(%1%/%2%,%3%)=>%4%");
            F%state->index()%state->id();
            F%s->name();
            ActionIndex i = offset+s->index();
            if (action_table_m.count(i)) {
                Transaction T = action_table_m.at(i);
                if (T.lookahead()==s->index()) {
                    ActionRef const action = coder().action(T.action(),s);
                    F%Description()(action,0);
                    output.insert(F.str());
                } else if (all) {
                    F%Description()(std::make_shared<Action>(Action::Type::ERROR,s),0);
                    output.insert(F.str());
                }
            } else if (all) {
                F%Description()(std::make_shared<Action>(Action::Type::ERROR,s),0);
                output.insert(F.str());
            }
        }
        offset = std::max(
                      min_reduce_offset()
                    , state->non_terminal_offset());
        for (SymbolRef const & s: generator().grammar()->reduce_symbols()) {
            Format F("(%1%/%2%,%3%)=>%4%");
            F%state->index()%state->id();
            F%s->name();
            ActionIndex i = offset+s->index();
            if (action_table_m.count(i)) {
                Transaction T = action_table_m.at(i);
                if (T.lookahead()==s->index()) {
                    ActionRef const action = coder().action(T.action(),s);
                    F%Description()(action,0);
                    output.insert(F.str());
                } else if (all) {
                    F%Description()(std::make_shared<Action>(Action::Type::ERROR,s),0);
                    output.insert(F.str());
                }
            } else if (all) {
                F%Description()(std::make_shared<Action>(Action::Type::ERROR,s),0);
                output.insert(F.str());
            }
        }
    }
    return output;
}
StringSet const Builder::simple_built_actions() const {
    StringSet output;
    for (StateRef const & state: generator().states()) {
        for (SymbolRef const & lookahead: generator().grammar()->lookahead_symbols()) {
            Format F("(%1%/%2%,%3%)=>%4%");
            F%state->index()%state->id();
            F%lookahead->name();
            ActionRef const action = coder().simple_action(state,lookahead);
            F%Description()(action,0);
            output.insert(F.str());
        }
    }
    return output;
}
#endif

LPP_NAMESPACE_END
